package com.itheima.leetcode.od.b.queue;

import java.util.*;

/**
 * <h3>模拟工作队列</h3>
 * 让我们来模拟一个工作队列的运作，有一个任务提交者和若干任务执行者，执行者从1开始编号 提交者会在给定的时刻向工作队列提交任务，任务有执行所需的时间， 执行者取出任务的时刻加上执行时间即为任务完成的时刻 执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，若这一时刻有多个空闲的执行者， 其中优先级最高的会执行这个任务。编号小的执行者优先级高。初始状态下所有执行者都空闲。 工作队列有最大长度限制，当工作队列满而有新的任务需要加入队列时，队列中最老的任务会被丢弃。 特别的，在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时， 队列中最老的任务被取出执行，新的任务加入队列。
 * <p>
 * 输入描述：
 * <p>
 * 输入为两行。 第一行为 2N 个正整数，代表提交者提交的N个任务的时刻和执行时间。 第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。 用例保证提交时刻不会重复，任务按提交时刻升序排列。 第二行为两个数字，分别为工作队列的最大长度和执行者的数量。 两行的数字都由空格分隔。N 不超过 20 ，数字为不超过 1000 的正整数
 * <p>
 * 输出描述：
 * <p>
 * 输出两个数字，分别为最后一个任务执行完成的时刻和被丢弃的任务的数量，数字由空格分隔。
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * 1 3 2 2 3 3
 * <p>
 * 3 2
 * <p>
 * 输出：
 * <p>
 * 7 0
 * <p>
 * 示例2：
 * <p>
 * 输入：
 * <p>
 * 1 6 2 4 4 3 6 3
 * <p>
 * 1 2
 * <p>
 * 输出：
 * <p>
 * 10 0
 * <p>
 * 示例3：
 * <p>
 * 输入：
 * <p>
 * 1 6 2 4 3 3 4 3 6 3
 * <p>
 * 1 2
 * <p>
 * 输出：
 * <p>
 * 10 1
 */
public class TaskScheduler {
    public static void main(String[] args) {
        /*Scanner input = new Scanner(System.in);
        JobConfig config = new JobConfig(input.nextLine().split(" "), input.nextLine().split(" "));*/

        String jobDataStr = "1 6 2 4 10 1";
        String systemParamsStr = "1 2";
        System.out.println(getResult(jobDataStr.split(" "), systemParamsStr.split(" ")));
    }

    private static String getResult(String[] jobData, String[] systemParams) {
        JobConfig config = new JobConfig(jobData, systemParams);

        Queue<Integer> pendingJobs = new LinkedList<>();
        int[] executorBusyUntil = new int[config.executorNum]; // 直到几点之前处理器busy 理解变量的作用&意义？
        int rejectedCount = 0;
        int finalFinishTime = 0;
        int jobIndex = 0;

        while (true) { // 得考虑任务添加完了的情况，此时这又阻塞队列和执行线程有任务
            if (jobIndex >= config.arrivalTime.size() && pendingJobs.isEmpty()) { // 所有任务都添加了 且 任务队列无等待任务
                break;
            }

            // 找下一个事件时间
            // 此时的时刻是 arrivalTime
            int nextTime = Integer.MAX_VALUE;
            if (jobIndex < config.arrivalTime.size()) {
                nextTime = config.arrivalTime.get(jobIndex);
            }
            // 这一步的意义是为了没有新的任务时候 配合 config.arrivalTime.get(jobIndex) == nextTime 继续处理 执行器 和 队列里的任务
            for (int busyTime : executorBusyUntil) {
                if (busyTime > 0) {
                    nextTime = Math.min(nextTime, busyTime);
                }
            }
            if (nextTime == Integer.MAX_VALUE) {
                break;
            }

            // 获取空闲执行器
            List<Integer> freeExecutors = new ArrayList<>();
            for (int i = 0; i < config.executorNum; i++) {
                if (executorBusyUntil[i] <= nextTime) {
                    freeExecutors.add(i);
                    executorBusyUntil[i] = 0;
                }
            }

            freeExecutors.sort((a, b) -> a - b); // 编号越小的执行器先执行
            int assignCount = Math.min(pendingJobs.size(), freeExecutors.size());
            for (int i = 0; i < assignCount; i++) { // 先处理阻塞队列的任务
                int taskId = pendingJobs.poll();
                int execId = freeExecutors.remove(0);
                executorBusyUntil[execId] = nextTime + config.processingTime.get(taskId);
            }

            while (jobIndex < config.arrivalTime.size() && config.arrivalTime.get(jobIndex) == nextTime) { // 不断循环处理到 == nextTime，循环过程中jobIndex不++
                if (!freeExecutors.isEmpty()) { // 处理完阻塞队列的任务仍然有空闲 执行器
                    int execId = freeExecutors.remove(0);
                    executorBusyUntil[execId] = nextTime + config.processingTime.get(jobIndex);
                } else if (pendingJobs.size() < config.queueCapacity) {
                    pendingJobs.offer(jobIndex);
                } else {
                    pendingJobs.poll(); // 队列满了新的任务也得进队 而且会顶掉最旧的任务
                    pendingJobs.offer(jobIndex);
                    rejectedCount++;
                }
                jobIndex++;
            }

            // 更新最终完成时间
            for (int time : executorBusyUntil) {
                finalFinishTime = Math.max(finalFinishTime, time);
            }
        }

        return finalFinishTime + " " + rejectedCount;
    }

    static class JobConfig {
        List<Integer> arrivalTime;
        List<Integer> processingTime;

        int queueCapacity;
        int executorNum;

        public JobConfig(String[] jobData, String[] systemParams) {
            arrivalTime = new ArrayList<>();
            processingTime = new ArrayList<>();
            for (int i = 0; i < jobData.length - 1; i += 2) {
                arrivalTime.add(Integer.parseInt(jobData[i]));
                processingTime.add(Integer.parseInt(jobData[i + 1]));
            }
            queueCapacity = Integer.parseInt(systemParams[0]);
            executorNum = Integer.parseInt(systemParams[1]);
        }
    }
}